package 逆波兰表达式求值;

import java.util.Stack;

public class Solution {
    /*
    给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
    请你计算该表达式。返回一个表示表达式值的整数。
    注意：
    有效的算符为 '+'、'-'、'*' 和 '/' 。
    每个操作数（运算对象）都可以是一个整数或者另一个表达式。
    两个整数之间的除法总是 向零截断 。
    表达式中不含除零运算。
    输入是一个根据逆波兰表示法表示的算术表达式。
    答案及所有中间计算结果可以用 32 位 整数表示。
     */
    public int evalRPN(String[] tokens) {
        // tokens中包含了两个类型的数据，一个是操作数，一个是运算符
        // 解决思路：
        // 1.遇到操作数就将操作数压入栈中
        // 2.遇到运算符就从栈中取出两个操作数，先取出的作为右操作数，后取出的作为左操作数
        // 3.计算的结果再次压入栈中
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String s = tokens[i];
            Integer a, b;
            switch (s) {
                case "+":
                    b = stack.pop();
                    a = stack.pop();
                    stack.push(a + b);
                    break;
                case "-":
                    b = stack.pop();
                    a = stack.pop();
                    stack.push(a - b);
                    break;
                case "*":
                    b = stack.pop();
                    a = stack.pop();
                    stack.push(a * b);
                    break;
                case "/":
                    b = stack.pop();
                    a = stack.pop();
                    stack.push(a / b);
                    break;
                default:
                    stack.push(stringToInteger(s));
            }
        }
        // 栈中报错的即为运算的结果
        return stack.pop();
    }

    private static Integer stringToInteger(String num) {
        int result = 0;
        int len = num.length();
        int i = 0;
        // 标记num是否为一个负数
        boolean flag = false;
        // 如果num是一个负数，则从1开始遍历num
        if (num.charAt(0) == '-') {
            i = 1;
            flag = true;
        }
        while (i < len) {
            char c = num.charAt(i);
            result = 10 * result + (c - '0');
            i++;
        }
        return flag ? -result : result;
    }
}
